package listbyorder.access201_300.test239;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/6/27 10:31
 */
public class Solution1 {

    // 解法一： 使用单调队列进行求解
    // 如果当前单调队列为null或者加入的元素小于等于尾部的元素，加入队列
    // 如果不满足上面的条件，将队列尾部的元素弹出
    public int[] maxSlidingWindow(int[] nums, int k) {
        int len = nums.length;
        if (len < 2) return nums;
        Deque<Integer> queue = new ArrayDeque<>();
        int[] res = new int[len - k + 1];
        int index = 0;
        for (int i = 0; i < len; i++) {
            if (i >= k) {
                if (queue.peekFirst() == nums[i - k]) {
                    queue.removeFirst();
                }
            }
            while (!queue.isEmpty() && nums[i] > queue.peekLast()) {
                queue.removeLast();
            }
            queue.addLast(nums[i]);
            if (i >= k - 1) {
                res[index++] = queue.peekFirst();
            }
        }
        return res;
    }
}
